package swordForOffer;

import java.util.*;

public class SwordForOffer {

    public static String TAG = "SwordForOffer";
    private static final int[] array1 = new int[] {1, 2, 3, 4, 5, 6};
    private static final int[] array2 = new int[] {-1, -2, 3, -4, 5, 6};
    private static final int[] array3 = new int[] {5,1,4,3};
    private static final int[] array4 = new int[] {10, 5, 2, 6};
    private static final int[] array5 = new int[] {1, 1, 1};

    public static void main(String[] args) {
        System.out.println("twoSum: " + Arrays.toString(twoSum(array1, 9)));
        System.out.println("threeSum: " + threeSum(array2));
        System.out.println("getShortArraySize: " + getShortArraySize(array3, 7));
        System.out.println("numSubArrayProductLessThanK: " + numSubArrayProductLessThanK(array4, 100));
        System.out.println("subArraySum: " + subArraySum(array5, 2));
    }

//----------------------------------------------------------------------------

    /**
     * C2-sub6 排序数组中的两个数字之和
     * 题目：输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？
     * 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
     * 例如，输入数组[1，2，4，6，10]，k的值为8，数组中的数字2与6的和为8，它们的下标分别为1与3。
     */
    public static int[] twoSum(int[] array, int k) {
        //双指针解题
        int smallIndex = 0;
        int bigIndex = array.length - 1;
        while (smallIndex < bigIndex && array[smallIndex] + array[bigIndex] != k) {
            if (array[smallIndex] + array[bigIndex] > k) {
                bigIndex--;
            } else {
                smallIndex++;
            }
        }
        return new int[] { smallIndex, bigIndex };
    }

//--------------------------------------------------------------------------------

    /**
     * C2-sub7 数组中和为0的3个数字
     * 题目：输入一个数组，如何找出数组中所有和为0的3个数字的三元组？
     * 需要注意的是，返回值中不得包含重复的三元组。
     * 例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们分别是[-1，0，1]和[-1，-1，2]。
     */
    public static List<List<Integer>> threeSum(int[] array) {
        //上一个题目的延伸
        List<List<Integer>> resultList = new ArrayList<>();
        if (array.length >= 3) {
            Arrays.sort(array);
            for (int i = 0; i < array.length - 2; i++) {
                twoSumWithResult(array, i, resultList);
                //注意：即使相等了也得继续执行，跳过相同的值，避免重复
                int temp = array[i];
                while (temp == array[i]) {
                    i++;
                }
            }
        }
        return resultList;
    }

    private static void twoSumWithResult(int[] array, int i, List<List<Integer>> resultList) {
        int j = i + 1;
        int k = array.length - 1;
        while (j < k) {
            int iNum = array[i];
            int jNum = array[j];
            int kNum = array[k];
            if (iNum + jNum + kNum == 0) {
                resultList.add(Arrays.asList(iNum, jNum, kNum));
                //跳过相同的值
                int temp = array[j];
                while (temp == array[j]) {
                    j++;
                }
            } else if (jNum + kNum > iNum) {
                k--;
            } else {
                j++;
            }
        }
    }
//---------------------------------------------------------------------------------------

    /**
     * C2-sub8 和大于或等于k的最短子数组
     * 题目：输入一个正整数组成的数组和一个正整数k
     * 请问数组中和大于或等于k的连续子数组的最短长度是多少？
     * 如果不存在所有数字之和大于或等于k的子数组，则返回0。
     * 例如，输入数组[5，1，4，3]，k的值为7，和大于或等于7的最短连续子数组是[4，3]，因此输出它的长度2。
     */
    public static int getShortArraySize(int[] array, int k) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for (int right = 0; right < array.length; right++) {
            sum += array[right];
            while (left <= right && sum >= k) {
                minLength = Math.min(minLength, right -left + 1);
                sum -= array[left];
                left++;
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    /**
     * 总结：从左往右遍历，遇到数组和大于目标值的子数组，再内部迭代看是否有更小的值；
     * 使用一个局部变量来保存最小长度，返回值时注意是否有赋值过，没有返回0；
     */
//-------------------------------------------------------------------------------------

    /**
     * C2-sub9 乘积小于K的子数组
     */
    public static int numSubArrayProductLessThanK(int[] nums, int k) {
        int left = 0;
        int count = 0;
        int sub = 1;
        for (int right = 0; right < nums.length; ++right) {
            //计算left->right数组元素的乘积
            sub *= nums[right];
            //当数组元素的乘积大于等于k，将left指针左移，并且去掉乘积里的left指针值
            while (left <= right && sub >= k) {
                sub /= nums[left++];
            }
            //计算本次循环中符合要求的子数组数量（子数组都是从left指针开始（left指针会向右移动，不需要考虑中间的子数组），所以个数即为数组元素个数）
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }

    /**
     * C2-sub10 和为k的子数组，nums是一个整数数组（没说正负数）
     */
    public static int subArraySum(int[] nums, int k) {
        //第1步：计算从0开始的每一个子数组的和
        Map<Integer, Integer> sumMap = new HashMap<>();
        int count = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            sumMap.put(i, sum);
        }
        //第2步：计算各个子数组之和差值等于k的数量，差值为k，即相差的数组为符合要求的数组
        for (int m = 0; m < nums.length; m++) {
            for (int n = m; n < nums.length; n++) {
                if (m == n && sumMap.get(m) == k) {
                    count++;
                }
                if (m < n && sumMap.get(n) - sumMap.get(m) == k) {
                    count++;
                }
            }
        }
        return count;
    }

    //书本参考代码,一开始不是很好理解
    public static int subArraySum2(int[] nums, int k) {
        Map<Integer, Integer> sumToCount = new HashMap<>(); //key为前i个数字之和,value为每个和出现的次数
        sumToCount.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num: nums) {
            sum += num;
            //获取之前是否有和为sum-k的子数组,当前数组与和为sum-k的子数组之前的子数组和即为k,sum-(sum-k) = k
            count += sumToCount.getOrDefault(sum - k, 0);
            sumToCount.put(sum, sumToCount.getOrDefault(sum, 0) + 1);
        }
        //遍历一遍即可获取满足要求的子数组数量
        return count;
    }

    /**
     * C3-sub18 有效的回文
     */
    public static boolean isPalindrome(String s) {
        //双指针法
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            char ch1 = s.charAt(i);
            char ch2 = s.charAt(j);
            //先忽略大小写
            if (!Character.isLetterOrDigit(ch1)) {
                i++;
            } else if (!Character.isLetterOrDigit(ch2)) {
                j--;
            } else {
                //转换大小写统一
                ch1 = Character.toUpperCase(ch1);
                ch2 = Character.toUpperCase(ch2);
                if (ch1 != ch2) {
                    //只要有一次不相同，则不符合要求
                    return false;
                } else {
                    i++;
                    j--;
                }
            }
        }
        return true;
    }

    /**
     * C3-sub18 有效的回文（最多删除一个字符）
     */
//    public static boolean isPalindromeWithDeleteOne(String s) {
//        //双指针法
//        boolean enableDelete = true;
//        return true;
//    }
}















